package com.fang.algorithm.zuo.linked;

/**
 * @author lingxiao.fang
 * @Desc 给定一个链表head，一个value，使得小于该value的节点都放在左边，等于该value的在中间，大于该value的节点都放在右边
 * @createTime 2025/2/23 21:09
 */
public class Test09_PartitionLinkedList {
    public static void main(String[] args) {
        Node head = new Node(11);
        Node temp = head;
        for (int i = 10; i > 1; i--) {
            temp.next = new Node(i);
            temp = temp.next;
        }
        Node partitionNode = partitionLinkedList1(head, 5);
//        Node partitionNode = partitionLinkedList2(head, 5);
        while (partitionNode != null) {
            System.out.print(partitionNode.value + "->");
            partitionNode = partitionNode.next;
        }
    }

    private static Node partitionLinkedList1(Node head, int part) {
        if (head == null || head.next == null) {
            return head;
        }
        Node temp = head;
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        Node[] help = new Node[length];
        temp = head;
        int index = 0;
        while (temp != null) {
            help[index] = temp;
            index++;
            temp = temp.next;
        }
        nodeArrPartition(help, part);
        Node ans = help[0];
        temp = ans;
        for (int i = 1; i < help.length; i++) {
            temp.next = help[i];
            temp = temp.next;
            if (i == help.length - 1) {
                temp.next = null;
            }
        }
        return ans;
    }

    private static void nodeArrPartition(Node[] nodeArr, int part) {
        int small = -1;
        int more = nodeArr.length;
        int index = 0;
        while (index < more) {
            if (nodeArr[index].value < part) {
                swap(nodeArr, index, small + 1);
                small++;
                index++;
            } else if (nodeArr[index].value > part) {
                swap(nodeArr, index, more - 1);
                more--;
            } else {
                index++;
            }
        }
    }

    private static void swap(Node[] arr, int i, int j) {
        Node temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }

}
